package com.stephen.data.linkedlist;

/**
 * @author: stephen
 * @create: 2020-01-30 20:22
 * @description: 单向环形链表,josephu问题
 */
public class Josephu {

    public static void main(String[] args) {
        CircleLinkedList list = new CircleLinkedList();
        list.addBoy(5);
        list.list();
        // 测试出圈
        list.countBoy(1,2,5);// 2->4->1->5->3
    }

}

class CircleLinkedList {
    // first节点
    public Boy first = null;

    /**
     *  根据要求计算出圈的节点
     * @param startNo 从第几个开始
     * @param countNum 数几下
     * @param nums 最初圈中节点的总个数
     */
    public void countBoy(int startNo,int countNum,int nums) {
        // 校验输入的数值
        if (first == null || startNo < 1 || startNo > nums) {
            System.out.println("输入数值有误,请重新输入");
            return;
        }
        // 需要一个辅助指针,帮助出圈
        Boy helper = first;

        // 1.移动helper,让它指向环形链表的最后一个节点,即first的前一个位置
        while (true) {
            if (helper.getNext() == first) {
                // 说明helper 指向了最后的节点
                break;
            }
            helper = helper.getNext();
        }

        // 2.把helper 和 first 移动到指定位置,即从哪个位置开始数数,
        //   移动 startNo -1 次
        for (int i = 0; i < startNo - 1; i++) {
            first = first.getNext();
            helper = helper.getNext();
        }

        // 3.让节点开始移动,让first 和 helper 指针同时移动 countNum - 1 次
        //   然后出圈
        while (true) {
            if (helper == first) {
                break; // 此时圈中只有一个节点
            }
            // helper 和 first 同时移动 countNum - 1 次
            for (int i = 0; i < countNum - 1; i++) {
                first = first.getNext();
                helper = helper.getNext();
            }
            // 此时 first 指向的节点,即为要出圈的节点
            System.out.printf("节点[%d] 出圈 \n",first.getNo());
            // 出圈之后的两个指针要发生变化
            // first 向下移动一个
            first = first.getNext();
            // helper 指向新的 first
            helper.setNext(first);
        }
        System.out.printf("最后留在圈中的节点编号为[%d] \n",helper.getNo());
    }

    /**
     * 构建单向环形链表
     * @param nums 链表节点总个数
     */
    public void addBoy(int nums) {
        if (nums < 1) {
            System.out.println("nums 大小不符合要求~~~");
            return;
        }
        // 定义一个辅助指针,来确定位置
        Boy curBoy = null;
        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                // 第一个节点
                first = boy;
                // 自己指向自己
                first.setNext(first);
                curBoy = first;
            } else {
                // 当前节点的next指向新的节点
                curBoy.setNext(boy);
                // 新的节点的next 指向 first
                boy.setNext(first);
                // curBoy 指向新的节点
                curBoy = boy;
            }
        }
    }

    /**
     * 遍历环形链表
     */
    public void list() {
        if (first == null) {
            System.out.println("链表为空");
            return;
        }
        Boy curBoy = first;
        // curBoy的next节点指向first时,说明已经遍历到最后
        while (true) {
            // 指针指向最后时,这个节点也需要打印
            // 先打印,后退出,否则会少一个节点
            System.out.printf("当前节点编号为[%d] \n",curBoy.getNo());
            if (curBoy.getNext() == first) {
                break;
            }
            curBoy = curBoy.getNext();
        }

    }
}

class Boy {
    private int no;
    private Boy next;

    public Boy(int no) {
        this.no = no;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public Boy getNext() {
        return next;
    }

    public void setNext(Boy next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "Boy{" +
                "no=" + no +
                '}';
    }
}